//----------------------------------------------------------------------高斯消元
//Z2上高斯消元求秩,用位压缩储存
int rank(long long a[],int n)
{
    int i,j;
    for(i=0;i<63;i++)
    {
        int mask=1<<i;
        for(j=i;j<n;j++)if(a[j]&mask){swap(a[i],a[j]);break;}
        for(j++;j<n;j++)if(a[j]&mask)a[j]^=a[i];
    }
    for(i=j=0;i<n;i++)if(a[i])j++;
    return j;
}

/*R上的高斯消元:
 * 	输入:
 * 		a[n][m+1] ----  [系数矩阵|常数列]
 * 		n,m   ----  系数矩阵的行数,列数
 * 	输出:
 * 		ret[n] ----  解空间
 * 		返回:
 * 			0:不满秩,无解;
 * 			1:正常
*/
#define eps 1e-8
int dcmp(double x){if(x>eps)return 1;if(x<-eps)return -1;return 0;}
int Gauss_elimination(double a[][60],int n,int m,double ret[])
{
	int i,j,k,r;//r=rank
	double tmp;
	for(i=r=0;i<m;i++)
	{
		for(j=r; j<n && !dcmp(a[j][i]) ;j++);
		if(j>=n)continue;
		if(j>r)
			for(k=0;k<=m;k++)SWAP(a[r][k],a[j][k]);
		for(j=0;j<n;j++)
			if(j!=r&&dcmp(a[j][i]))
			{
				tmp=a[j][i]/a[r][i];
				for(k=0;k<=m;k++)a[j][k]-=tmp*a[r][k];
			}
		r++;
	}
	for(i=0;i<n;i++)if(dcmp(a[i][m]))
	{
		for(j=0;j<m&&!dcmp(a[i][j]);j++);
		if(j==m)return 0;
		else ret[j]=a[i][m]/a[i][j];
	}
	return 1;
}
